import heapq
from typing import List


class Solution:
    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:
        n = len(charge)
        # 时间, 剩余电, 点
        graph = [[] for _ in range(n)]
        inf = float('inf')
        min_time = [[inf for _ in range(cnt+1)] for _ in range(n)]
        min_time[start][0] = 0
        heap = [(0,0,start)]
        for u,v,w in paths:
            graph[u].append((v,w))
            graph[v].append((u,w))
        while heap:
            t, battery, node = heapq.heappop(heap)
            if node == end: return t
            if t < min_time[node][battery]: continue
            for new_battery in range(battery, cnt+1):
                min_time[node][new_battery] = min(min_time[node][new_battery],min_time[node][new_battery-1]+charge[node])
                for nex,weight in graph[node]:
                    if weight > new_battery: continue
                    arrive_time = min_time[node][new_battery] + weight
                    if min_time[nex][new_battery-weight] <= arrive_time: continue
                    min_time[nex][new_battery - weight] = arrive_time
                    heapq.heappush(heap,(min_time[nex][new_battery-weight], new_battery-weight,nex))
        return -1

if __name__ == '__main__':
    s = Solution()
    r = s.electricCarPlan(paths = [[1,3,3],[3,2,1],[2,1,3],[0,1,4],[3,0,5]], cnt = 6, start = 1, end = 0, charge = [2,10,4,1])
    print(r)